package com.fyl.leetcode.binarySearch;

/**
 * @author:fyl
 * @date 2021/5/13 20:29
 * @Modified By:
 * @Modified Date:
 * @Description:
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 *
 * 利用二分思想先找其左边界，再找其右边界即可，注意找左边界的时候，由右侧逼近；找右边界的时候，由左侧逼近，即可。
 */
public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = findFirst(nums,target,true);
        result[1] = findFirst(nums,target,false);
        return result;
    }

    //lower为true找左边界 false找右边界
    //利用二分思想先找其左边界，再找其右边界即可，注意找左边界的时候，由右侧逼近；找右边界的时候，由左侧逼近，即可。
    public int findFirst(int[] nums, int target, boolean lower) {
        int low = 0;
        int high = nums.length - 1;
        int mid = 0, res = -1;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (nums[mid] > target) {
                high = mid - 1;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                res = mid;
                //处理target == nums[mid]
                if (lower) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return res;
    }
}
